/*
2021-11-9
https://leetcode-cn.com/problems/maximum-path-quality-of-a-graph/
*/
const int  M = 1010, N = 110;
typedef pair<int, int> PII;
class Solution {
private:
    vector<PII> p[M];
    vector<int> v;
    int ans=0;
    int st[M];
public:
    void dfs(int u,int sum,int cost,int tm)
    {
        if(cost>tm) return ;
        if(st[u]==0) 
            sum+=v[u];
        if(u==0) ans=max(ans,sum);
        st[u]++;
        for(auto t:p[u])
        {
            dfs(t.first,sum,cost+t.second,tm);
        }
        st[u]--;
    }
    int maximalPathQuality(vector<int>& values, vector<vector<int>>& edges, int maxTime) {
        v=values;
        for(auto t:edges)
        {
            p[t[0]].push_back({t[1],t[2]});
            p[t[1]].push_back({t[0],t[2]});
        }
        dfs(0,0,0,maxTime);
        return ans;
    }
};
